package 剑指offer;

/**
 * @Description:
 * @Author: Administrator
 * @Date: 2020-05-03
 */
class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }

}

public class 复杂链表的复制 {
    public static void main(String[] args) {
        RandomListNode root = new RandomListNode(1);
        root.next = new RandomListNode(2);
        root.next.next = new RandomListNode(3);
        root.next.next.next = new RandomListNode(4);
        root.random = root.next.next;
        root.next.random = root.next.next.next;
        print(root);
        print(Clone(root));
    }

    public static  void print(RandomListNode node) {
        while (node != null) {
            System.out.print(node.label+"\t");
            if (node.random != null) {
                System.out.print(node.random.label+"\t");
            }
            node = node.next;
        }
    }
    public static RandomListNode Clone(RandomListNode pHead) {

        if(pHead==null) return null;
        RandomListNode temp = new RandomListNode(pHead.label);
        if (pHead.next == null) {
            return temp;
        }

        RandomListNode one = pHead;
        RandomListNode currNode = temp;
        while (one.next != null) {
            currNode.next = new RandomListNode(one.next.label);
            one = one.next;
            currNode = currNode.next;
        }
        RandomListNode two = temp;

        RandomListNode node1 = temp;
        RandomListNode node2 = pHead;
        while (two != null) {
            RandomListNode node3 = node1;
            RandomListNode node4 = node2;
            RandomListNode ran = node4.random;
            if (ran != null) {
                 node3 = temp;
                 node4 = pHead;
                while (node4 != null && node4 != ran) {
                    node4 = node4.next;
                    node3 = node3.next;
                }
                two.random = node3;
            }
            node1 = node1.next;
            node2 = node2.next;
            two = two.next;
        }
        return temp;

    }
}
